package DoExercise.HSP_ZCY.A010_排序算法系列;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @Author: Du
 * @Date: 2021/7/9 11:26
 */
public class A005_归并排序3
{
    public static class MyHeap<T>
    {
        private ArrayList<T> heap;
        private HashMap<T, Integer> indexMap;
        private int heapSize;
        private Comparator<? super T> comparator;
        
        public MyHeap(Comparator<? super T> com)
        {
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
            heapSize = 0;
            comparator = com;
        }
        
        public boolean isEmpty()
        {
            return heapSize == 0;
        }
        
        public int size()
        {
            return heapSize;
        }
        
        public boolean contains(T key)
        {
            return indexMap.containsKey(key);
        }
        
        public void push(T value)
        {
            heap.add(value);
            indexMap.put(value, heapSize);
            heapInsert(heapSize++);
        }
        
        public T pop()
        {
            T ans = heap.get(0);
            int end = heapSize - 1;
            swap(0, end);
            heap.remove(end);
            indexMap.remove(ans);
            heapify(0, --heapSize);
            return ans;
        }
        
        //修改类中的某个属性值后，在继续排序
        public void resign(T value)
        {
            Integer valueIndex = indexMap.get(value);
            if (valueIndex == null) return;
            heapInsert(valueIndex);
            heapify(valueIndex, heapSize);
        }
        
        private void heapInsert(int index)
        {
            while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0)
            {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
        
        private void heapify(int index, int heapSize)
        {
            int left = index * 2 + 1;
            while (left < heapSize)
            {
                int right = left + 1;
                int largest = right < heapSize && (comparator.compare(heap.get(right), heap.get(left)) < 0)
                        ? right
                        : left;
                largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
                if (largest == index)
                {
                    break;
                }
                swap(largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }
        
        private void swap(int i, int j)
        {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            heap.set(i, o2);
            heap.set(j, o1);
            indexMap.put(o1, j);
            indexMap.put(o2, i);
        }
        
    }
    
    public static class Student
    {
        public int classNo;
        public int age;
        public int id;
        
        public Student(int c, int a, int i)
        {
            classNo = c;
            age = a;
            id = i;
        }
        
    }
    
    public static class StudentComparator implements Comparator<Student>
    {
        
        @Override
        public int compare(Student o1, Student o2)
        {
            return o1.age - o2.age;
        }
        
    }
    
    public static void main(String[] args)
    {
        Student s1 = null;
        Student s2 = null;
        Student s3 = null;
        Student s4 = null;
        Student s5 = null;
        Student s6 = null;
        
        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);
        
        PriorityQueue<Student> heap = new PriorityQueue<>(new StudentComparator());
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        heap.add(s6);
        while (!heap.isEmpty())
        {
            Student cur = heap.poll();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }
        
        System.out.println("===============");
        
        MyHeap<Student> myHeap = new MyHeap<>(new StudentComparator());
        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);
        myHeap.push(s5);
        myHeap.push(s6);
        while (!myHeap.isEmpty())
        {
            Student cur = myHeap.pop();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }
        
        System.out.println("===============");
        
        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);
        
        heap = new PriorityQueue<>(new StudentComparator());
        
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        heap.add(s6);
        
        s2.age = 6;
        s4.age = 12;
        s5.age = 10;
        s6.age = 84;
        
        while (!heap.isEmpty())
        {
            Student cur = heap.poll();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }
        
        System.out.println("===============");
        
        s1 = new Student(2, 50, 11111);
        s2 = new Student(1, 60, 22222);
        s3 = new Student(6, 10, 33333);
        s4 = new Student(3, 20, 44444);
        s5 = new Student(7, 72, 55555);
        s6 = new Student(1, 14, 66666);
        
        myHeap = new MyHeap<>(new StudentComparator());
        
        myHeap.push(s1);
        myHeap.push(s2);
        myHeap.push(s3);
        myHeap.push(s4);
        myHeap.push(s5);
        myHeap.push(s6);
        
        s2.age = 6;
        myHeap.resign(s2);
        s4.age = 12;
        myHeap.resign(s4);
        s5.age = 10;
        myHeap.resign(s5);
        s6.age = 84;
        myHeap.resign(s6);
        
        while (!myHeap.isEmpty())
        {
            Student cur = myHeap.pop();
            System.out.println(cur.classNo + "," + cur.age + "," + cur.id);
        }
        
    }
}
